/**
 * 项目名：	Rumba Plan
 * 
 * 版权所有(C)，上海海鼎信息工程股份有限公司，2008，所有权利保留。
 * 
 * 文件名：	VGraph.java
 * 模块说明：	
 * 修改历史：
 * Jan 10, 2008 - linhui - 创建。
 */
package com.hd123.rumba.upgrade.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 有向图。
 * 
 * @author linhui
 * 
 */
public class VGraph {
  private List<String> nodes; // 有向图定点的集合
  private int[] dist; // 存放产生最短路径后，各节点到起始节点的距离
  private int[] path; // 存放产生最短路径后，各节点的的前一个节点下标
  private boolean[] visited; // 节点是否被访问过的状态集合
  private int[][] matrix; // 邻接矩阵
  private List<VEdge> edges; // 有向图边的集合

  /**
   * 增加一条边。
   * 
   * @param from
   *          边的起始顶点
   * @param to
   *          边的终止顶点
   */
  public void addEdge(String from, String to) {
    int fromIndex, toIndex;

    if (!nodes.contains(from)) {
      nodes.add(from);
      fromIndex = nodes.size() - 1;
    } else
      fromIndex = nodes.indexOf(from);

    if (!nodes.contains(to)) {
      nodes.add(to);
      toIndex = nodes.size() - 1;
    } else
      toIndex = nodes.indexOf(to);

    VEdge edge = new VEdge(fromIndex, toIndex);
    if (!edges.contains(edge))
      edges.add(edge);
  }

  public VGraph() {
    nodes = new ArrayList<String>();
    edges = new ArrayList<VEdge>();
  }

  /**
   * 对给定的边构造邻接矩阵，并初始化dist,path,visited
   */
  protected void initSearch() {
    int size = nodes.size();
    dist = new int[size];
    path = new int[size];
    visited = new boolean[size];
    matrix = new int[size][size];
    for (int i = 0; i < size; i++)
      for (int j = 0; j < size; j++)
        matrix[i][j] = Integer.MAX_VALUE;

    for (int i = 0; i < size; i++)
      matrix[i][i] = 0;
    for (VEdge edge : edges) {
      matrix[edge.getFrom()][edge.getTo()] = 1;
    }
  }

  /**
   * 搜索两个节点间的最短路径，结构存放于path中
   * 
   * @param from
   *          起始节点的下标
   * @param to
   *          终止节点的下标
   */
  protected void search(int from, int to) {
    for (int i = 0; i < nodes.size(); i++) {
      dist[i] = matrix[from][i];
      visited[i] = false;
      if (i != from && dist[i] < Integer.MAX_VALUE)
        path[i] = from;
      else
        path[i] = -1;
    }

    visited[from] = true;
    dist[from] = 0;
    for (int i = 0; i < nodes.size() - 1; i++) {
      int min = Integer.MAX_VALUE;
      int next = from;
      for (int j = 0; j < nodes.size(); j++)
        if (!visited[j] && dist[j] < min) {
          next = j;
          min = dist[j];
        }
      visited[next] = true;
      if (next == to || next == from)
        break;
      for (int k = 0; k < nodes.size(); k++) {
        if (!visited[k] && matrix[next][k] < Integer.MAX_VALUE
            && dist[next] + matrix[next][k] < dist[k]) {
          dist[k] = dist[next] + matrix[next][k];
          path[k] = next;
        }
      }
    }
  }

  /**
   * 获取两个节点间的最短路径
   * 
   * @param from
   *          起始节点
   * @param to
   *          终止节点
   * @return 返回最短路径上的各个节点
   */
  public List<String> getShortestPath(String from, String to) {
    int fromIndex = nodes.indexOf(from);
    int toIndex = nodes.indexOf(to);
    if (fromIndex < 0 || toIndex < 0)
      return new ArrayList<String>();
    return getShortestPath(fromIndex, toIndex);
  }

  /**
   * 获取两个节点间的最短路径
   * 
   * @param fromIndex
   *          起始节点下标
   * @param toIndex
   *          终止节点下标
   * @return 返回最短路径上的各个节点
   */
  protected List<String> getShortestPath(int fromIndex, int toIndex) {
    initSearch();
    search(fromIndex, toIndex);

    int p = toIndex;
    List<String> result = new ArrayList<String>();
    while (path[p] != -1 && p != fromIndex) {
      result.add(nodes.get(p));
      p = path[p];
    }
    if (p == fromIndex)
      result.add(nodes.get(p));
    Collections.reverse(result);
    return result;
  }

  // Getter
  protected List<String> getNodes() {
    return nodes;
  }

  protected int[] getDist() {
    return dist;
  }

  protected int[] getPath() {
    return path;
  }

  protected boolean[] getVisited() {
    return visited;
  }

  protected int[][] getMatrix() {
    return matrix;
  }

  protected List<VEdge> getEdges() {
    return edges;
  }
}
